//
//$Id: generate.cpp 630 2011-01-27 17:40:06Z andrew.tsyganov $
#include "stdafx.h"
#include "math.h"
#include "include/generate.h"
#include "include/utils.h"
#include "include/fa_utils.h"
#include "contrib/rapidxml/rapidxml.hpp"

using namespace std;
using namespace rapidxml;

bool Generate::load_XML(string const& file)
{
	init_Default();

	// process Generate node
	vector<char> buffer;
	xml_document<> doc;
	xml_node<>* gen_node = GetNode(file, buffer, doc, kGenerateXmlNode);

	if (gen_node == NULL)
	{
		return false;
	}

	// process generator node
	gen_node = gen_node->first_node(kGenerateXmlGeneratorNode.c_str(), 0, false);

	if (gen_node != NULL)
	{
		string s = ToLower(gen_node->value());
		generator_ = ((s == "fa_leslie") || (s == "fa_ladybird") ? s : "fa_leslie");
	}

	bool res = true;

	res &= fa_lep_.load_XML(file);
	res &= fa_lbp_.load_XML(file);
	
	return res;
}

bool FA_Leslie_Parameters::load_XML(string const& file)
{
	// process Generate node
	vector<char> buffer;
    xml_document<> doc;
	xml_node<>* node;
	xml_node<>* gen_node = GetNode(file, buffer, doc, kGenerateXmlNode);

	if (gen_node == NULL)
	{
		return false;
	}

	// process FA_Leslie nodes
	gen_node = gen_node->first_node(kGenerateXmlFALeslieNode.c_str(), 0, false);

	if (gen_node == NULL)
	{
		return false;
	}

	node = gen_node->first_node(kGenerateXmlFNamePfxNode.c_str(), 0, false);

	if (node != NULL)
	{
		fname_pfx_ = node->value();
	}

	node = gen_node->first_node(kGenerateXmlSeedNode.c_str(), 0, false);

	if (node != NULL)
	{	
		seed_ = atoi(node->value());
	}

	node = gen_node->first_node(kGenerateXmlSampleSizeNode.c_str(), 0, false);

	if (node != NULL)
	{	
		sample_size_ = atoi(node->value());
	}

	node = gen_node->first_node(kGenerateXmlSymbolsNumNode.c_str(), 0, false);

	if (node != NULL)
	{	
		symbols_num_ = atoi(node->value());
	}

	node = gen_node->first_node(kGenerateXmlStatesNumNode.c_str(), 0, false);

	if (node != NULL)
	{	
		states_num_ = atoi(node->value());
	}

	node = gen_node->first_node(kGenerateXmlInitialNumNode.c_str(), 0, false);

	if (node != NULL)
	{	
		initial_num_ = atoi(node->value());
	}

	node = gen_node->first_node(kGenerateXmlFinalNumNode.c_str(), 0, false);

	if (node != NULL)
	{	
		final_num_ = atoi(node->value());
	}

	node = gen_node->first_node(kGenerateXmlTransitionDensityNode.c_str(), 0, false);

	if (node != NULL)
	{	
		transition_density_ = atof(node->value());
	}

	node = gen_node->first_node(kGenerateXmlTypeNode.c_str(), 0, false);

	if (node != NULL)
	{	
		std::string s = ToLower(node->value());
		type_ = ( (s == "nfa") || (s== "dfa") ? s : "nfa");
	}

	node = gen_node->first_node(kGenerateXmlInequivalentNode.c_str(), 0, false);

	if (node != NULL)
	{	
		string s = ToLower(node->value());
		inequivalent_ = ( (s == "yes") || (s == "true") ? true : false);
	}

	return true;
}


bool FA_Ladybird_Parameters::load_XML(string const& file)
{
	// process Generate node
	vector<char> buffer;
    xml_document<> doc;
	xml_node<>* node;
	xml_node<>* gen_node = GetNode(file, buffer, doc, kGenerateXmlNode);

	if (gen_node == NULL)
	{
		return false;
	}

	// process FA_Ladybird nodes
	gen_node = gen_node->first_node(kGenerateXmlFALadybirdNode.c_str(), 0, false);

	if (gen_node == NULL)
	{
		return false;
	}

	node = gen_node->first_node(kGenerateXmlFNamePfxNode.c_str(), 0, false);

	if (node != NULL)
	{
		fname_pfx_ = node->value();
	}

	node = gen_node->first_node(kGenerateXmlStatesMinNode.c_str(), 0, false);

	if (node != NULL)
	{
		states_min_ = atoi(node->value());
	}

	node = gen_node->first_node(kGenerateXmlStatesMaxNode.c_str(), 0, false);

	if (node != NULL)
	{
		states_max_ = atoi(node->value());
	}

	return true;
}

void Generate::run(string const& dir) const
{
	if (generator_ == "fa_leslie")
	{
		GenerateFALeslie(dir, fa_lep_);
	}

	if (generator_ == "fa_ladybird")
	{
		GenerateFALadybird(dir, fa_lbp_);
	}
}

void GenerateFALeslie(string const& dir, FA_Leslie_Parameters const& fa_lep)
{
    random_generator rnd(0);
	rnd.randomize(1, fa_lep.seed_, 0);

    vector<FA> v_fa(fa_lep.sample_size_), v_dfa(fa_lep.sample_size_);

    cout << "Automata generation... " << flush;

    for (u_t i = 0; i < fa_lep.sample_size_; ++i)
    {
		
        FA fa;

        for(;;)
        {
			FALeslie(fa, fa_lep, rnd);

			fa.set_Name(fa.get_Name() + IntToStringZ(i, fa_lep.sample_size_ - 1));

            //cout << "generated!" << endl;
            
            bool det = fa.is_Deterministic();

			if (det && (fa_lep.type_ == "nfa"))
            {
                //cout << "deterministic!" << endl;
                continue;
            }

            if (!det && (fa_lep.type_ == "dfa"))
            {
                //cout << "nondeterministic!" << endl;
                continue;
            }

			if (!fa_lep.inequivalent_)
            {
                v_fa[i] = fa;
                break;
            }

            FA dfa;

            if (det)
            {
                dfa = fa;
				Label dead("dead");
                dfa.make_Dense(dead);
            }
            else
            {
                MinimizeBrzozowski(fa, dfa);
            }

            bool equiv_found = false;

            for (u_t j = 0; j < i; ++j)
            {
                vector<u_t> vu;
                bool equiv = AreIsomorphicDFAs(v_dfa[j], dfa, vu);
                
                if (equiv)
                {
                    equiv_found = true;
                    break;
                }
            }

            if (equiv_found)
			{
                continue;
			}
            else
            {
                v_fa[i] = fa;
                v_dfa[i] = dfa;
                break;
            }
        }

        cout << i << (i < fa_lep.sample_size_ - 1 ? ", " : " ");
    }
 
    cout << " done" << endl << flush;

	SaveFAs(v_fa, dir);
}

void FALeslie(FA& fa, FA_Leslie_Parameters const& fa_lep, random_generator& rnd)
{
	fa.init(fa_lep.fname_pfx_, fa_lep.symbols_num_, fa_lep.states_num_);

    // generate initial states
    Subset s;
	s.insert_range(0, fa_lep.states_num_ - 1);

	for (u_t i = 0; i < fa_lep.initial_num_; ++i) 
    {
        u_t index = rnd.next_UInt((unsigned int) s.size());
        u_t id = s.get_By_Count(index);
		fa.set_Initial(id);
        s.remove(id);
    };

    // generate final states
    s.remove();
	s.insert_range(0, fa_lep.states_num_ - 1);

    for (u_t i = 0; i < fa_lep.final_num_; ++i) 
    {
        u_t index = rnd.next_UInt((unsigned int) s.size());
        u_t id = s.get_By_Count(index);
		fa.set_Final(id);
        s.remove(id);
    };

    // generate transitions to eliminate inaccessible states
    Subset in, fin, visited, not_visited;

    s.remove();
	s.insert_range(0, fa_lep.states_num_ - 1);

	in = fa.get_Initial();
    visited = in;

    for (u_t i = 0; i < fa_lep.initial_num_; ++i)
    {
        // randomly choose some initial state
        u_t index1  = rnd.next_UInt((unsigned int) in.size());
        u_t from_id = in.get_By_Count(index1);
        in.remove(from_id);
        

        // randomly choose any OTHER state
        s.remove(from_id);
        u_t index2   = rnd.next_UInt((unsigned int) s.size());
        u_t to_id    = s.get_By_Count(index2);
        visited.insert(to_id);
        s.insert(from_id);

        // randomly choose a symbol
		u_t symbol_id = rnd.next_UInt((unsigned int) fa_lep.symbols_num_);
        
        // add a transition
        fa.add_Transition(from_id, symbol_id, to_id);
    }

    not_visited  = s;
	not_visited -= visited;

    while (!not_visited.empty())
    {
        u_t index1   = rnd.next_UInt((unsigned int) visited.size());
        u_t from_id  = visited.get_By_Count(index1);

        u_t index2   = rnd.next_UInt((unsigned int) not_visited.size());
        u_t to_id    = not_visited.get_By_Count(index2);
        not_visited.remove(to_id);
        visited.insert(to_id);

        u_t symbol_id = rnd.next_UInt((unsigned int) fa_lep.symbols_num_);
        
        fa.add_Transition(from_id, symbol_id, to_id);
    }

    // generate transitions to remove useless states
    s.remove();
	s.insert_range(0, fa_lep.states_num_ - 1);

	fin = fa.get_Final();
    visited = fin;
    not_visited.remove();

	for (u_t i = 0; i < fa_lep.final_num_; ++i)
    {
        // randomly choose some initial state
        u_t index1 = rnd.next_UInt((unsigned int) fin.size());
        u_t to_id  = fin.get_By_Count(index1);
        fin.remove(to_id);
        

        // randomly choose any OTHER state
        s.remove(to_id);
        u_t index2   = rnd.next_UInt((unsigned int) s.size());
        u_t from_id  = s.get_By_Count(index2);
        visited.insert(from_id);
        s.insert(to_id);

        // randomly choose a symbol
        u_t symbol_id = rnd.next_UInt((unsigned int) fa_lep.symbols_num_);
        
        // add a transition
        fa.add_Transition(from_id, symbol_id, to_id);

    }

    not_visited  = s;
    not_visited -= visited;

    while (!not_visited.empty())
    {
        u_t index1   = rnd.next_UInt((unsigned int) visited.size());
        u_t to_id  = visited.get_By_Count(index1);

        u_t index2   = rnd.next_UInt((unsigned int) not_visited.size());
        u_t from_id  = not_visited.get_By_Count(index2);
        not_visited.remove(from_id);
        visited.insert(from_id);

        u_t symbol_id = rnd.next_UInt((unsigned int) fa_lep.symbols_num_);
        
        fa.add_Transition(from_id, symbol_id, to_id);
    }

    // add transitions to achieve proper transition density
	u_t transitions_num = (u_t) ceil(fa_lep.transition_density_ * (double) (fa_lep.states_num_ * fa_lep.states_num_ * fa_lep.symbols_num_));

    while (fa.get_Transitions_Num() < transitions_num)
    {
        u_t from_id   = rnd.next_UInt((unsigned int) fa_lep.states_num_);
        u_t to_id     = rnd.next_UInt((unsigned int) fa_lep.states_num_);
        u_t symbol_id = rnd.next_UInt((unsigned int) fa_lep.symbols_num_);

        fa.add_Transition(from_id, symbol_id, to_id);
    }
}

void GenerateFALadybird(string const& dir, FA_Ladybird_Parameters const& fa_lbp)
{
	for (u_t states_num = fa_lbp.states_min_; states_num <= fa_lbp.states_max_; ++states_num)
	{
		FA fa;

		fa.init("ladybird_" + IntToString(states_num), 3, states_num);

		vector<Label> alphabet(3);
		alphabet[0] = (string) "a";
		alphabet[1] = (string) "b";
		alphabet[2] = (string) "c";

		fa.set_Symbols(alphabet);


		fa.add_Transition(states_num - 1, 0, 0);
		for (u_t i = 1; i < states_num; ++i)
		{
			fa.add_Transition(i - 1, 0, i);
			fa.add_Transition(i, 1, i);
			fa.add_Transition(i, 2, i);
			fa.add_Transition(i, 2, 0);
		}

		fa.set_Initial(0);
		fa.set_Final(0);

		fa.save_XML(CreatePath(dir, fa.get_Name() + ".xml"));
	}
}

//EOF!
